package algorithms.sorting

/**
 * [Insertion Sort - Part 1](https://www.hackerrank.com/challenges/insertionsort1)
 */
// Complete the insertionSort1 function below.
fun insertionSort1(n: Int, arr: Array<Int>): Unit {
    val temp = arr.last()
    for (i in n - 2 downTo 0) {
        if (arr[i] > temp) {
            arr[i + 1] = arr[i]
            println(arr.joinToString(" "))
        } else {
            arr[i + 1] = temp
            println(arr.joinToString(" "))
            return
        }
    }
    arr[0] = temp
    println(arr.joinToString(" "))
}

/**
 * [Insertion Sort - Part 2](https://www.hackerrank.com/challenges/insertionsort2)
 */
// Complete the insertionSort2 function below.
fun insertionSort2(n: Int, arr: Array<Int>): Unit {
    fun insertion(m: Int, arr1: Array<Int>) {
        val temp = arr1[m - 1]
        for (i in m - 2 downTo 0) {
            if (arr1[i] > temp) {
                arr1[i + 1] = arr1[i]
            } else {
                arr1[i + 1] = temp
                return
            }
        }
        arr1[0] = temp
    }

    for (i in 2..n) {
        insertion(i, arr)
        println(arr.joinToString(" "))
    }
}